package oj;

//相交链表：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
public class Solution_160 {
    private static int sizeOf(ListNode head){
        int size = 0;
        for(ListNode cur = head;cur != null;cur = cur.next){
            size++;
        }
        return size;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int sizeA = sizeOf(headA);
        int sizeB = sizeOf(headB);
        //比较两个链表的大小，如果不相等就使得长度相等，这样便于同时遍历链表
        if(sizeA > sizeB){
            int d = sizeA - sizeB;
            for(int i = 0;i < d;i++){
                headA = headA.next;
            }
        }else if(sizeA < sizeB){
            int d = sizeB - sizeA;
            for(int i = 0;i < d;i++){
                headB = headB.next;
            }
        }else{
            //长度相等不用进行改变
        }
        ListNode curA = headA;
        ListNode curB = headB;
        while(curA != curB){
            curA = curA.next;
            curB = curB.next;
        }
        //这里返回curA和curB度可以，如果有相交结点那么curA == curB，如果没有相交结点，那么两个链表就会遍历到最后，curA == curB == null
        return curA;
    }
}
